#pragma once

#include<iostream>
#include<utility>
#include<algorithm>
#include<string>
#include<vector>

template<class T>
struct HashFunc
{
	size_t operator()(const T& key)
	{
		return (size_t)key;
	}
};
template<>
struct HashFunc<std::string>
{
	
	size_t operator()(const std::string& str )
	{
		size_t hash=0;
		for(auto &e :str)
		{
			hash *= 133;
			hash += e;
		}
		return hash;
	}
};
typedef enum STATUS
{
	EMPTY,
	EXIST,
	DELETE
}Status;
template<class K, class V>
struct Elem
{
	std::pair<K, V> _kv;
	Status _state;
	Elem() : _state(EMPTY) {}
};
template<class K,class V>
class HashTable
{
	void CheckCapacity()
	{
		if ((_size*10)/_ht.capacity()>7)
		{
			HashTable tmp(_ht.capacity() * 2);
			for (auto& e : _ht)
			{
				if (e._state == EXIST)
					tmp.insert(e._kv);
			}
			swap(tmp);
		}
	}
public:
	HashTable(size_t capacity = 3) :_ht(capacity), _size(0) {}
	
	bool insert(const std::pair<K, V>& kv)
	{
		CheckCapacity();
		HashFunc<K> fun;
		size_t HashAddr = fun(kv.first);
		HashAddr %= _ht.capacity();
		while (_ht[HashAddr]._state != EMPTY)
		{
			if (_ht[HashAddr]._kv.first == kv.first && _ht[HashAddr]._state == EXIST)
				return false;
			if (_ht[HashAddr]._state == DELETE)
				break;
			HashAddr = (HashAddr + 1) % _ht.capacity();

		}
		_ht[HashAddr]._kv = kv;
		_ht[HashAddr]._state = EXIST;
		_size++;
		return true;
	}
	void swap(HashTable<K, V>& ht)
	{
		std::swap(_ht, ht._ht);
		std::swap(_size, ht._size);
	}

	bool erase(const K& key)
	{
		HashFunc<K> hash;
		int hashaddr = hash(key);
		hashaddr %= (_ht.capacity());
		while (_ht[hashaddr]._state != EMPTY)
		{
			if (_ht[hashaddr]._state == EXIST && _ht[hashaddr]._kv.first == key)
			{
				_ht[hashaddr]._state = DELETE;
				return true;
			}
			hashaddr = (hashaddr + 1) % _ht.capacity();
		}
		return false;
	}

	bool empty()
	{
		return _size == 0;
	}
	size_t size()
	{
		return _size;
	}
private:
	

	std::vector<Elem<K,V>> _ht;
	size_t _size;

};


template<class K,class V>
struct HashNode
{
	struct HashNode* _next;
	std::pair<K, V> _kv;
	struct HashNode(const std::pair<K, V>& kv) :_kv(kv), _next(nullptr) {}
};
template<class K,class V>
class hashtable
{
	typedef HashNode<K, V> Node;
	void CheckCapacity()
	{
		if (_size == _ht.capacity())
		{
			hashtable<K, V> tmp(_ht.capacity() * 2);
			HashFunc<K> hash;
			for (auto& e : _ht)
			{
				Node* cur = e;
				
				while (cur)
				{
					Node* next  = cur->_next;
					int hashaddr = (hash(cur->_kv.first)) % tmp._ht.capacity();
					cur->_next = tmp._ht[hashaddr];
					tmp._ht[hashaddr] = cur;
					cur = next;
				}
				e = nullptr;
			}
			tmp._size = _size;
			swap(tmp);
		}
	}
	void swap(hashtable<K,V>& hs)
	{
		std::swap(_size, hs._size);
		std::swap(_ht, hs._ht);
	}
public:
	hashtable(size_t capacity = 30) :_ht(capacity), _size(0) {}

	bool insert(const std::pair<K,V> &kv)
	{
		CheckCapacity();
		HashFunc<K> hash;
		Node* newnode = new Node(kv);
		int hashaddr= hash(kv.first) % _ht.capacity();
		newnode->_next = _ht[hashaddr];
		_ht[hashaddr] = newnode;
		++_size;
		return true;
	}
	Node* find(const K& key)
	{
		HashFunc<K> hash;
		int hashaddr = hash(key) % _ht.capacity();
		if (_ht[hashaddr])
		{
			Node* cur = _ht[hashaddr];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				cur = cur->_next;
			}
		}
		return nullptr;
	}

	bool erase(const K& key)
	{
		HashFunc<K> hash;
		int hashaddr = hash(key) % _ht.capacity();
		if (_ht[hashaddr])
		{
			Node* cur = _ht[hashaddr];
			if (cur->_kv.first == key)
			{
				_ht[hashaddr] = cur->_next;
				delete cur;
				--_size;
				return true;
			}
			while (cur->_next)
			{
				if (cur->_next->_kv.first== key)
				{
					Node* del = cur->_next;
					cur->_next = cur->_next->_next;
					delete cur;
					--_size;
					return true;
				}
				cur = cur->_next;
			}			
		}
		return false;
	}

private:
	std::vector<Node*> _ht;
	size_t _size;
};
